package com.jojo.elementary.day11_tree;

import com.jojo.elementary.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 104、二叉树的最大深度
 *
 * 给定一个二叉树，找出其最大深度。
 *
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 示例：
 * 给定二叉树 [3,9,20,null,null,15,7]，
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回它的最大深度3
 */
public class TreeMaxDepth {

    /** myCode 层序遍历（广度优先遍历） */
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        int count = 0;
        List<TreeNode> tree = new ArrayList<>();
        tree.add(root);
        while (!tree.isEmpty()){
            count++;
            //临时的每层所有节点
            List<TreeNode> temp = new ArrayList<>();
            for (TreeNode treeNode : tree) {
                if (treeNode.left != null){
                    temp.add(treeNode.left);
                }
                if (treeNode.right != null){
                    temp.add(treeNode.right);
                }
            }
            tree = temp;
        }
        return count;
    }

    /** myCode 递归（深度优先遍历） */
    public int maxDepth2(TreeNode root) {
        if (root == null){
            return 0;
        }
        int leftDepth = maxDepth2(root.left);
        int rightDepth = maxDepth2(root.right);
        return Math.max(leftDepth,rightDepth) + 1;
    }
}
